package middle;

import util.PrintUtils;

public class Solution_240 {

    public static void main(String[] args) {
        Solution_240 model = new Solution_240();
        System.out.println(model.searchMatrix(new int[][]{{1, 4, 7, 11, 15}, {2, 5, 8, 12, 19}, {3, 6, 9, 16, 22}, {10, 13, 14, 17, 24}, {18, 21, 23, 26, 30}}, 5));
        System.out.println(model.searchMatrix(new int[][]{{1,4,7,11,15},{2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30}}, 20));
//        PrintUtils.transfer("[[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]");
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        for (int[] ints : matrix) {
            if (ints[0] > target) {
                return false;
            }
            boolean flag = find(ints, target);
            if (flag) {
                return true;
            }
        }
        return false;
    }

    private boolean find(int[] array, int target) {
        int begin = 0, end = array.length;
        while (begin + 1 < end) {
            int mid = (begin + end) >> 1;
            if (array[mid] == target) {
                return true;
            } else if (array[mid] < target) {
                begin = mid + 1;
            } else {
                end = mid;
            }
        }
        return begin < array.length && array[begin] == target;
    }
}
